Cho đồ thị G=(X, E).

Bước 1: Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần.Bước 2: Khởi tạo T:= ØBước 3: Lần lượt lấy từng cạnh thuộc danh sách đã sắp xếp. Nếu T+{e} không chứa chu trình thì gán T:=T+{e}.Bước 4: Nếu T đủ n-1 phần tử thì dừng, ngược lại làm tiếp bước 3.

Kỹ thuật đánh nhãn đỉnh

Kỹ thuật đánh nhãn đỉnhTrong thuật toán Kruskal, để kiểm tra xem T + {e} có chứa chu trình hay không ta có thể dùng kỹ thuật gắn nhãn đỉnh, kỹ thuật này khá đơn giản và hiệu quả.

• Ngay sau bước 1 của thuật toán, ta gắn đỉnh i của đồ thị một nhãn là i
• Trong bước 2:
  • Nếu hai đầu cạnh e có cùng nhãn (tức là nhãn của e.v1 và nhãn của e.v2 bằng nhau) thì T+{e} tạo chu trình, ta không đưa e vào T.
  • Ngược lại [nếu Label(e.v1)!= Label(e.v2) ] thì ta đưa e vào T và thực hiện công việc ghép nhãn bằng cách:
    • lab1 = Min(Label(e.v1), Label (e.v2))
    • lab2 = Max(Label(e.v1), Label (e.v2))
    • Sửa nhãn của tất cả các đỉnh nào có nhãn là lab2 thành nhãn lab1

Ghi chú

• Trong quá trình xây dựng T thì các cạnh có thể không liên thông nhau lúc đó T chỉ là rừng chứ chưa trở thành cây.
• Khi thuật toán dừng:
  • Nếu T chưa đủ n - 1 cạnh thì đồ thị G không liên thông(không có cây khung)
  • Ngược lại thì T là cây khung cần tìm.